public class code03ss {
    // 虽然但是，超市了。。。
    public int findKthLargest(int[] nums, int k) {
        // 解法三：使用快速排序，将整个数组进行排序之后，尝试找到第 k 大的值

        // 针对快速排序，实现一个方法，需要传入下面的这些参数
        int len = nums.length - 1;

        Quicksort(nums, 0, len);

        // 在排序完成后，直接返回第 nums.length - k 下标上的值即可
        return nums[nums.length - k];
    }

    public void Quicksort(int[] arr, int low, int high) {

        if(low >= high) {
            return;
        }

        // 首先第一步，将值传入到排序操作中，尝试找到一个基准
        int flag = getFlag(arr, low, high);
        Quicksort(arr, low, flag - 1);
        Quicksort(arr, flag + 1, high);
    }

    public int getFlag(int[] arr, int low, int high) {
        // 将当前的最左侧的值记录为基准点
        int flag = low;
        // 记录下左侧基准点的值
        int pivot = arr[low];

        while(low < high) {
            while(low < high && arr[high] >= pivot) {
                // 只要右侧高点的值大于 基准点，就将右侧指针前移
                high--;
            }
            while(low < high && arr[low] <= pivot) {
                low++;
            }
            // 也就是当出现 low 指向的值 大于 high 指向的值时
            // 此时进行交换操作
            swap(arr, low, high);
        }

        // 循环整体结束后
        // 需要将 low 的值和 基准点的值进行交换
        swap(arr, low, flag);

        // 之后将新的 low 作为基准点返回
        return low;
    }

    public void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}
